#!/usr/bin/python3
import sys

try:
    t = input()
    t = int(t)
    list_ret = []
    while t > 0:
        n, m = input().split()
        i = 1
        j = 0
        if n != "" and m != "":
            n = int(n)
            m = int(m)
            if n <= sys.maxsize and m <= sys.maxsize:
                while 1:
                    i = i + m
                    if i <= n:
                        j = j + 1
                    elif i % n != 1:
                        i = i % n
                        j = j + 1
                    else:
                        j = j + 1
                        list_ret.append(j)
                        break
            else:
                break
            t = t - 1
        else:
            break
    for i, ret in enumerate(list_ret, 0):
        print("Case #%s: %s" % (i + 1, ret))
except ValueError:
    pass
except EOFError:
    pass
except MemoryError:
    pass
